#include <stdio.h>
#include <string.h>
#include <cstdlib>
typedef int ElementType; // 元素类型 (typedef作用是起别名)

//双向链表节点结构体
typedef struct DNode {
    ElementType data; // 数据域
    struct DNode* prev; // 前驱指针域
    struct DNode* next; // 后继指针域
}DNode;

//初始化双向链表
DNode* InitList() { // 初始化双向链表(返回指针的函数,语法不懂可看菜鸟教程)
    DNode* head = (DNode*)malloc(sizeof(DNode)); // 分配头结点内存
    head->data = 0; // 头结点数据域置0
    head->prev = head; // 头结点前驱指针域指向自己
    head->next = head; // 头结点后继指针域指向自己
    return head; // 返回头结点指针
}

DNode* inserhead(DNode* head, ElementType data) //头插法插入元素
{
    DNode* newNode = (DNode*)malloc(sizeof(DNode)); // 创建新节点
    newNode->data = data; // 设置新节点数据
    newNode->prev = head; // 新节点前驱指向头结点
    newNode->next = head->next; // 新节点后继指向头结点后继
    head->next->prev = newNode; // 头结点后继前驱指向新节点
    head->next = newNode; // 头结点后继指向新节点
    return head; // 返回头结点指针
}

// 指定位置插入元素
int inserMid(DNode* head, int position, ElementType data) {
    if (position < 1) return 0; // 位置非法
    DNode* p = head; // 指向头结点
    int i = 0;
    // 找到插入位置的前一个节点
    while (i < position-1 && p->next != head) {
        p = p->next;
        i++;
    }
    if (i != position-1) return 0; // 位置超出链表长度
    DNode* newNode = (DNode*)malloc(sizeof(DNode)); // 创建新节点
    newNode->data = data;  // 设置新节点数据
    newNode->prev = p;      // 新节点前驱指向p
    newNode->next = p->next;  // 新节点后继指向p的后继
    p->next->prev = newNode;  //  p的后继前驱指向新节点
    p->next = newNode;
    return 1; // 插入成功
}

// 尾插法
int insertTail(DNode* head, ElementType data) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode)); // 创建新节点
    newNode->data = data; // 设置新节点数据
    newNode->next = head; // 新节点后继指向头结点
    newNode->prev = head->prev; // 新节点前驱指向头结点前驱
    head->prev->next = newNode; // 头结点前驱后继指向新节点
    head->prev = newNode; // 头结点前驱指向新节点
    return 1; // 插入成功
}

// 遍历双向链表
void PrintList(DNode* head) {
    DNode* p = head->next; // 指向第一个节点
    while (p != head) { // 遍历链表直到回到头结点
        printf("%d ", p->data); // 打印节点数据
        p = p->next; // 指向下一个节点
    }
    printf("\n");
}

//删除指定位置节点
int deleteNode(DNode* head, int position) {
    if (position < 1) return 0; // 位置非法
    DNode* p = head; // 指向头结点
    int i = 0;
    // 找到删除位置的前一个节点
    while (i < position-1 && p->next != head) {
        p = p->next;
        i++;
    }
    if (i != position-1 || p->next == head) return 0; // 位置超出链表长度
    DNode* toDelete = p->next; // 要删除的节点
    p->next = toDelete->next; // 前驱节点指向后继节点
    toDelete->next->prev = p; // 后继节点前驱指向前驱节点
    free(toDelete); // 释放删除节点内存
    return 1; // 删除成功
}

int clearList(DNode* head) { // 清空双向链表
    DNode* p = head->next; // 指向第一个节点
    while (p != head) { // 遍历链表直到回到头结点
        DNode* toDelete = p; // 要删除的节点
        p = p->next; // 指向下一个节点
        free(toDelete); // 释放删除节点内存
    }
    head->next = head; // 头结点后继指向自己
    head->prev = head; // 头结点前驱指向自己
    return 1; // 清空成功
}

int main(){
    DNode* head = InitList(); // 初始化双向链表
    inserhead(head, 10); // 头插法插入元素10
    inserhead(head, 20); // 头插法插入元素20
    inserhead(head, 30); // 头插法插入元素30
    PrintList(head); // 打印链表
    inserMid(head, 2, 15); // 在位置2插入元素15
    PrintList(head); // 打印链表
    deleteNode(head, 4); // 删除位置3的节点
    PrintList(head); // 打印链表
    clearList(head); // 清空链表
    PrintList(head); // 打印链表
    return 0;
}